/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM40 重建二叉树 (根据前序和中序遍历重建二叉树）
 * <a href="https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=295&tqId=23282&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2023-01-02
 * Time: 22:43
 */
//题目中的规定：
//      1.vin.length == pre.length
//      2.pre 和 vin 均无重复元素
//      3.vin出现的元素均出现在 pre里
//      4.只需要返回根结点，系统会自动输出整颗树做答案对比
import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode (int val) {
        this.val = val;
    }
}

public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre,int[] vin) {
        int len1 = pre.length;
        int len2 = vin.length;
        //递归终止条件
        if (len1 == 0 || len2 == 0) {
            return null;
        }
        //创建根节点
        int val = pre[0];
        TreeNode root = new TreeNode(val);
        //在中序遍历数组中找到val所处位置（不需要考虑重复值）
        for (int i = 0; i < vin.length; i++) {
            //递归下去
            if (val == vin[i]) {
                //构建左子树
                root.left = reConstructBinaryTree(
                        Arrays.copyOfRange(pre,1,i+1),
                        Arrays.copyOfRange(vin,0,i));
                //构建右子树
                root.right = reConstructBinaryTree(
                        Arrays.copyOfRange(pre,i+1,len1),
                        Arrays.copyOfRange(vin,i+1,len2));
            }
        }
        return root;
    }
}